﻿class Solution
{
public:
	// 逆序链表 
	ListNode* reverse(ListNode* head)
	{
		ListNode* newHead = new ListNode(0);
		ListNode* cur = head;
		while (cur)
		{
			ListNode* next = cur->next;
			cur->next = newHead->next;
			newHead->next = cur;
			cur = next;
		}
		cur = newHead->next;
		delete newHead;
		return cur;
	}
	ListNode* addInList(ListNode* head1, ListNode* head2)
	{
		// 1. 逆序 
		head1 = reverse(head1);
		head2 = reverse(head2);
		// 2. ⾼精度加法 
		int t = 0;
		ListNode* cur1 = head1, * cur2 = head2;
		ListNode* ret = new ListNode(0);
		ListNode* prev = ret;
		while (cur1 || cur2 || t)
		{
			if (cur1)
			{
				t += cur1->val;
				cur1 = cur1->next;
			}
			if (cur2)
			{
				t += cur2->val;
				cur2 = cur2->next;
			}
			prev = prev->next = new ListNode(t % 10);
			t /= 10;
		}
		cur1 = ret->next;
		ret->next = nullptr;
		delete ret;
		return reverse(cur1);
	}
};